/*
 * @lc app=leetcode id=106 lang=cpp
 *
 * [106] Construct Binary Tree from Inorder and Postorder Traversal
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = postorder.size();
        if (len < 1) {
            return NULL;
        }
        return buildTree(postorder, 0, len-1, inorder, 0, len-1);   
    }

    TreeNode* buildTree(vector<int>& po, int pst, int ped, vector<int>& io, int ist, int ied) {
        if (pst > ped) {
            return NULL;
        } else if (pst == ped) {
            return new TreeNode(po[pst]);
        }

        int val = po[ped];
        int len = 0;
        TreeNode* root = new TreeNode(val);
        for (int i=ist; i<=ied; i++) {
            if (io[i] == val) {
                len = i-ist;
                break;
            }
        }

        root->left = buildTree(po, pst, pst+len-1, io, ist, ist+len-1);
        root->right = buildTree(po, pst+len, ped-1, io, ist+1+len, ied);
        return root;
    }
};

